#include<cstdio>//uncle-lu
#include<algorithm>
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }
	while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	x = f ? -x : x;
	return ;
}

struct node{
	int v,w;
};
node objects[101];

int list[101];
int ex[101][5];
int n,m,top;
int F[32010];

int main()
{
	int c;
	read(m);read(n);

	for(int i=1;i<=n;++i)
	{
		read(objects[i].v);read(objects[i].w);read(c);

		if(!c)
		{
			top++;
			list[top] = i;
		}
		else
		{
			ex[c][0]++;
			ex[c][ ex[c][0] ] = i;
		}
	}

	for(int i=1;i<=top;++i)
	{
		int t = list[i];
		for(int j=m;j>=objects[t].v;j--)
		{
			F[j]  = std::max(F[j],F[j-objects[t].v] + objects[t].v * objects[t].w);

			if(ex[t][0]>0)
			{
				if(j>=objects[t].v + objects[ ex[t][1] ].v)F[j] = std::max(F[j],F[j-objects[t].v-objects[ ex[t][1] ].v] + objects[t].v * objects[t].w + objects[ ex[t][1] ].v * objects[ ex[t][1] ].w);
				if(j>=objects[t].v + objects[ ex[t][2] ].v)F[j] = std::max(F[j],F[j-objects[t].v-objects[ ex[t][2] ].v] + objects[t].v * objects[t].w + objects[ ex[t][2] ].v * objects[ ex[t][2] ].w);
				if(j>=objects[t].v + objects[ ex[t][1] ].v + objects[ ex[t][2] ].v)F[j] = std::max(F[j],F[j-objects[t].v-objects[ ex[t][1] ].v - objects[ ex[t][2] ].v ] + objects[t].v * objects[t].w + objects[ ex[t][1] ].v * objects[ ex[t][1] ].w + objects[ ex[t][2] ].v * objects[ ex[t][2] ].w );
			}
		}
	}
	printf("%d",F[m]);

	return 0;
}
